#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/**
 * quicksort
*/
int part(int *r, int low, int high) {
    int piv = r[low];
    int i = low, j = high;
    while(i < j) {
        while(i < j && r[j] > piv) --j;
        if(i < j) swap(r[i++], r[j]);
        while(i < j && r[i] <= piv) ++i;
        if(i < j) swap(r[i], r[j--]);
    }
}
void quickSort(int *r, int low, int high) {
    int mid;
    if(low < high) {
        mid = part(r, low, high);
        quickSort(r, low, mid-1);
        quickSort(r, mid+1, high);
    }
}
/**
 * mergesort
*/
void merge(int *r, int low, int mid, int high) {
    int *a = new int[high-low+1];
    int i = low, j = mid+1, k = 0;
    while(i <= mid && j <= high) {
        if(r[i] <= r[j]) {
            a[k++] = r[i++];
        }else {
            a[k++] = r[j++];
        }
    }
    while(i <= mid) {
        a[k++] = r[i++];
    }
    while(j <= high) {
        a[k++] = r[j++];
    }
    k = 0;
    for(int i = low; i <= high; ++i) {
        r[i] = a[k++];
    }
    delete[] a;
}
void mergesort(int *r, int low, int high) {
    if(low < high) {
        int mid = (low + high) / 2;
        mergesort(r, low, mid);
        mergesort(r, mid+1, high);
        merge(r, low, mid, high);
    }
}

int main() {
    int a[] = {3,2,1,5,4,3,2,1};
    mergesort(a, 0, 7);
    for(auto x : a) {
        cout << x << " ";
    }
}